1143. 最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

代码

func longestCommonSubsequence(text1 string, text2 string) int {
	len1 := len(text1)
	len2 := len(text2)
	if len1 == 0 || len2 == 0 {
		return 0
	}

	dp := make([][]int, len1+1)

	for i := range dp {
		dp[i] = make([]int, len2+1)
	}

	for i := 1; i <= len1; i++ {
		for j := 1; j <= len2; j++ {
			if text1[i-1] == text2[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}

	return dp[len1][len2]
}

这一题的核心思想是，选或者不选

如果遍历时，
当前的两个字符相等，那么必须选，那么就是：

这里加的1就代表选中了当前的值，$dp[i-1][j-1]$ 代表不选i，不选j的最大值

如果两个字符不相等，那就是有三种情况，那就是：

1. 不选i，选j
2. 选i，不选j
3. 不选i，不选j

因为【不选i，不选j】这种情况被前两种包含进去了，所以代码中可以省略

最终的转移方程：